package seqlist.leetcode;

//删除链表中所有值为val节点
public class Num203 {
    public static void main(String[] args) {
        //创建一个链表
        //[1,2,6,3,4,5,6]
        ListNode head=build();
        Num203 num203=new Num203();
        ListNode newHead=num203.removeElements(head,6);
        System.out.println(newHead);
        System.out.println(num203.toString(newHead));

    }

    //输出
    public String toString(ListNode head){
        String ret="";
        ListNode node=head;
        while(node!=null){
            ret+=node.val;
            ret+="->";
            node=node.next;
        }
        ret+="null";
        return ret;
    }
    //虚拟头节点法
    public ListNode removeElements(ListNode head,int val){
        ListNode dummyHead=new ListNode(-1);
        dummyHead.next=head;
        ListNode prev=dummyHead;
        while (prev.next!=null){
            if(prev.next.val==val){
                prev.next=prev.next.next;
            }else {
                prev=prev.next;
            }
        }
        return dummyHead.next;
    }

    //删除当前链表中所有值为val的节点,返回删除后链表的头节点
    public ListNode removeElements2(ListNode head,int val){
        //头节点就须删除
        while (head!=null&&head.val==val){
            head=head.next;
        }
        if(head==null){
            return null;
        }else {
            ListNode prev=head;
            while (prev.next!=null){
                if(prev.next.val==val){
                    ListNode cur=prev.next;
                    prev.next=cur.next;
                    cur.next=null;
                }else {
                    prev=prev.next;
                }
            }
        }
        return head;
    }

    //递归
    public ListNode removeElements3(ListNode head,int val){
        if(head.next==null){
            return null;
        }
        head.next=removeElements3(head.next,val);
        if(head.val==val){
            return head.next;
        }else {
            return head;
        }
    }

    public static ListNode build(){
        ListNode node1=new ListNode(1);
        ListNode node2=new ListNode(2);
        ListNode node3=new ListNode(6);
        ListNode node4=new ListNode(3);
        ListNode node5=new ListNode(4);
        ListNode node6=new ListNode(5);
        ListNode node7=new ListNode(6);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;
        node6.next=node7;
        return node1;
    }
}
